package graph;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import util.Graphs;

/**
 *
 * @author Admin
 */
public class TreeImplement<V, E extends Graph.Edge<V>> implements Tree<V, E> {

    private Graph<V, E> graph;
    private V root;

    public TreeImplement(Graph<V, E> graph, V root) {
        if (!Graphs.isTree(graph)) {
            throw new IllegalArgumentException("Invalid tree");
        }
        this.graph = graph;
        if (!graph.containsVertex(root)) {
            throw new IllegalArgumentException("Invalid root");
        }
        this.root = root;
    }

    public V root() {
        return root;
    }

    public Set<V> nodes() {
        return graph.vertices();
    }

    public int degree(V v) {
        return graph.degree(v);
    }

    public Set<V> neighbors(V v) {
        Set<V> set = new HashSet<V>();
        for (E e : graph.incidentEdges(v)) {
            set.add(e.getOpposite(v));
        }
        return set;
    }

    public Iterable<V> children(V v) {
        return graph.successors(v);
    }

    public V father(V v) {
        Iterator<V> loop = graph.predecessors(v).iterator();
        if (loop.hasNext()) {
            return loop.next();
        } else {
            throw new NullPointerException();
        }
    }

    /**
     * get root shrubs (rooted at treeRoot->children)
     *
     * @return
     */
    public ArrayList<Shrub<V, E>> shrubs() {
        ArrayList<Shrub<V, E>> list = new ArrayList<Shrub<V, E>>();
        for (V child : children(root)) {
            // Tr[v,i]
            list.add(getShrub(child));
        }
        return list;
    }

    /**
     * get sub shrub rooted at rootPlus (rooted at treeRoot->r+->rootPlus)
     *
     * @param rootPlus
     * @return
     */
//    private Shrub<V, E> getShrub(V shrubRoot, V rootPlus) {
    private Shrub<V, E> getShrub(V rootPlus) {

//        Map<V, Set<V>> nodes = new TreeMap<V, Set<V>>(new Comparator<V>() {
//            @Override
//            public int compare(V v1, V v2) {
//                int rs = Integer.compare(graph.degree(v1), graph.degree(v2));
//                return rs == 0 ? -1 : rs;
//            }
//        });
        Map<V, Set<V>> nodes = new HashMap<V, Set<V>>();
        ArrayList<V> indices = new ArrayList<V>();
        for (V vi : children(rootPlus)) {
            Set<V> children = new HashSet<V>();
            // children of each vi
            for (V child : children(vi)) {
                children.add(child);
            }
            indices.add(vi);
            nodes.put(vi, children);
        }

//        return new Shrub<V, E>(shrubRoot, rootPlus, nodes, indices);
        return new Shrub<V, E>(this, rootPlus, nodes, indices);

    }

    public boolean isEmpty() {
        return root == null;
    }

    public Graph<V, E> innerGraph() {
        return graph;
    }

    // other methods to use tree easier
    @Override
    public String toString() {
        return graph.toString();
    }
}
